package java学习.代码随想录.动态规划;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/9/10 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 不相交的线 {
    /**
     * 我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
     *
     * 现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，
     *      （1）只要 A[i] == B[j]，
     *      （2）且我们绘制的直线不与任何其他连线（非水平线）相交。
     *
     * 以这种方法绘制线条，并返回我们可以绘制的最大连线数。
     */

    /**              0 1 2            0 1 2
     * 输入：nums1 = [1,4,2], nums2 = [1,2,4]
     * 输出：2
     *              1 2 4
     *
     * dp[0][0] = 1  dp[1][1] = 1 , dp[1][0] = 1  dp[0][1] = 1
     * dp[1][2] = 2  dp[2][1] = 1   dp[2][2] = 2
     *
     *      1 4 2
     *      0 0 0
     *  1 0 1 1 1
     *  2 0 1 1 2
     *  4 0 1 2 2
     *
     * 输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
     * 输出：3
     *
     * dp[0][0] = 0
     *
     *
     */

    public static int maxUncrossedLines(int[] nums1, int[] nums2) {
        int [][] dp = new int[nums1.length+1][nums2.length+1];
        for (int i = 0; i <nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i]==nums2[j]){
                    dp[i+1][j+1] = dp[i][j]+1;
                }else {
                    dp[i+1][j+1] = Math.max(dp[i+1][j],dp[i][j+1]);
                }

            }
        }
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print (dp[i][j]+" ");
            }
            System.out.println();
        }
        return dp[nums1.length][nums2.length];
    }

    public static void main(String[] args) {
//        int [] nums1 = {1,4,2}, nums2 = {1,2,4};
        int [] nums1 = {2,5,1,2,5},
              nums2 = {10,5,2,1,5,2};
//        int[] nums1 = {1,3,7,1,7,5}, nums2 = {1,9,2,5,1};
//        输出：2
        maxUncrossedLines(nums1,nums2);
    }
}
